package interviewCode;

import java.util.Arrays;

public class SearchInterview {
    public static void main(String[] args) {
/**
 * LeetCode35：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中
 * 返回它将会被按照顺序插入的位置。
 * */
        int array[] = {1, 3, 5, 7};
//        System.err.println(search(array, 7));
//
//        System.err.println(search1(array, 4));

        System.out.println(searchInsert(array,2));
    }
/**
 * leetcode最妙解法
 * */
    public static int searchInsert(int[] nums, int target) {
        for(int i = 0; i < nums.length;i++){
            if(nums[i] >= target){
                return i;
            }
        }
        return nums.length;

    }

    /**
     * 方法1：排序后查找
     */
    public static int search(int nums[], int target) {

        int array2[] = null;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            } else {
                array2 = Arrays.copyOf(nums, nums.length + 1);
                array2[array2.length - 1] = target;
            }
        }
        return sort(array2, target);
    }

    public static int sort(int temp1[], int target) {
        //冒泡排序
        for (int i = 0; i < temp1.length - 1; i++) {

            for (int j = 0; j < temp1.length - 1 - i; j++) {

                if (temp1[j] > temp1[j + 1]) {
                    int temp = temp1[j];

                    temp1[j] = temp1[j + 1];

                    temp1[j + 1] = temp;
                }
            }
        }

        return search(temp1, target);
    }

    /**
     * 二分查找
     * */
    public static int search1(int char1[], int target) {

        int array2[] = null;
        for (int i = 0; i < char1.length; i++) {
            if (char1[i] == target) {

                return i;
            } else {
                array2 = Arrays.copyOf(char1, char1.length + 1);
                array2[array2.length - 1] = target;
            }
        }
        return binarySearch(array2, target);
    }

    public static int binarySearch(int[] srcArray, int des) {
        //定义初始最小、最大索引
        int start = 0;
        int end = srcArray.length - 1;
        //确保不会出现重复查找，越界
        while (start <= end) {
            //计算出中间索引值
            int middle = (end + start)>>>1 ;//防止溢出
            if (des == srcArray[middle]) {
                return middle;
                //判断下限
            } else if (des < srcArray[middle]) {
                end = middle - 1;
                //判断上限
            } else {
                start = middle + 1;
            }
        }
        //若没有，则返回-1
        return search1(srcArray, des);
    }
}
